package main

import (
	"fmt"
	"math"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//用时5%，内存19%，看来这道题用bfs解不占优势
func minDepth1(root *TreeNode) int {
	if root == nil {
		return 0
	}
	queue := []*TreeNode{}
	count := []int{}
	queue = append(queue, root)
	count = append(count, 1)
	for i := 0; i < len(queue); i++ {
		node := queue[i]
		depth := count[i]
		if node.Left == nil && node.Right == nil {
			return depth
		}
		if node.Left != nil {
			queue = append(queue, node.Left)
			count = append(count, depth+1)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
			count = append(count, depth+1)
		}
	}
	return 0
}

//递归方法,叶子节点的定义为没有子节点，所以到达叶子节点应该是到达没有子节点的叶子节点，用时60%，内存22%
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	} else if root.Left == nil {
		return minDepth(root.Right) + 1
	} else if root.Right == nil {
		return minDepth(root.Left) + 1
	} else {
		return int(math.Min(float64(minDepth(root.Left)), float64(minDepth(root.Right)))) + 1
	}
}

func main() {
	t1 := TreeNode{1, nil, nil}
	t2 := TreeNode{Val: 2}
	fmt.Println(minDepth(&t1))
	fmt.Println(minDepth1(&t2))

}
